package com.zklh.leetcode.other.problem509;
/**
 * @descrpiton 关于斐波那契数算法实现
 * @author 坐看落花
 * @version 1.0
 * @date 2019/10/12
 */
public class Solution {

    // 存储f(i)的计算结果, i对应数组的下标
    private int[] results;
    /**
     * 使用动态规划, 优化递归方法, 减少相同子问题的重复计算
     * @param n
     * @return
     */
    public int fib(int n){
        if(results == null){
            results = new int[n];
            results[1] = 1;
        }
        if(n == 0){
            return 0;
        }else if( n == 1){
            return 1;
        }

        /* 在这里进行剪枝 */
        // 分别代表f(n-1)和f(n-2)的值)
        int leftValue,rightValue;
        if(results[n-1] != 0){
            leftValue = results[n-1];
        }else{
            leftValue = fib(n-1);
            results[n-1] = leftValue;
        }
        if(results[n-2] != 0 || n-2 == 0){
            rightValue = results[n-2];
        }else{
            rightValue = fib(n-2);
            results[n-2] = rightValue;
        }
        return leftValue + rightValue;
    }

    /**
     * 这里使用普通的递归方法实现的, 效率比用上动态规划的方式的效率低一些
     * @param //n
     * @return
     */
    /*public int fib(int n){
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }
        // 递归关系
        return fib(n-1) + fib(n-2);
    }*/

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.fib(4));
    }
}

